﻿// Copyright (c) 2014 Morten Bakkedal
// This code is published under the MIT License.

using System;
using System.Collections.Generic;

using FuncLib.DualFunctions.Collections;

namespace FuncLib.DualFunctions.Compilation
{
	public class DualCompiler
	{
		private DualFunction[] functions;
		private List<DualFunction> sortedFunctions;
		private Dictionary<DualFunction, List<DualFunction>> outOfScopeMap;

		private DualCompiler(DualFunction[] functions)
		{
			this.functions = functions;
		}

		/// <summary>
		/// Compiles a function including all partial derivatives up to the orders specified by the variables.
		/// </summary>
		public static CompiledDualFunction Compile(DualFunction function)
		{
			return Compile(new DualFunction[] { function })[0];
		}

		/// <summary>
		/// Compiles a group of functions including all partial derivatives up to the orders specified by the variables.
		/// </summary>
		public static CompiledDualFunction[] Compile(DualFunction[] functions)
		{
			return new DualCompiler(functions).Compile();
		}

		private CompiledDualFunction[] Compile()
		{
			Sort();


			throw new NotImplementedException();
			//return null;
		}

		private void Sort()
		{
			// Build the dependency graph non-recursively. Recursion causes a stack overflow for complex functions; the ). Uses more memory
			// during the partial sorting, but is probably faster.

			HashSet<DualFunction> waitingFunctions = new HashSet<DualFunction>(functions);
			Dictionary<DualFunction, List<DualFunction>> dependencyMap = new Dictionary<DualFunction, List<DualFunction>>();
			Stack<DualFunction> nextFunctions = new Stack<DualFunction>();

			Dictionary<DualFunction, HashSet<DualFunction>> reverseDependencyMap = new Dictionary<DualFunction, HashSet<DualFunction>>();

			while (true)
			{
				DualFunction currentFunction = null;
				foreach (DualFunction waitingFunction in waitingFunctions)
				{
					// Take out the next waiting function (no particular order).
					currentFunction = waitingFunction;
					break;
				}

				if (currentFunction == null)
				{
					// No more functions. All dependencies have been determined.
					break;
				}

				List<DualFunction> dependencies = new List<DualFunction>();
				foreach (DualFunction dependency in currentFunction.GetDependencies())
				{
					if (dependencies.Contains(dependency))
					{
						// Already added, e.g. a binary operation with the same operand and the left and right.
						continue;
					}

					dependencies.Add(dependency);
					if (!waitingFunctions.Contains(dependency) && !dependencyMap.ContainsKey(dependency))
					{
						waitingFunctions.Add(dependency);
					}

					if (!reverseDependencyMap.ContainsKey(dependency))
					{
						reverseDependencyMap[dependency] = new HashSet<DualFunction>();
					}
					if (!reverseDependencyMap[dependency].Contains(currentFunction))
					{
						reverseDependencyMap[dependency].Add(currentFunction);
					}
				}

				if (dependencies.Count == 0)
				{
					// No dependencies (i.e. no incoming edges). Start with these functions.
					nextFunctions.Push(currentFunction);
					//nextFunctions.Add(currentFunction);
				}

				// Now this function has been processed.
				waitingFunctions.Remove(currentFunction);
				dependencyMap.Add(currentFunction, dependencies);
			}

			// The next step is to perform the topological sorting. Using the first algorithm from here:
			// http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=458591470#Algorithms

			//Console.WriteLine("start");
			//System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
			sortedFunctions = new List<DualFunction>();
			while (nextFunctions.Count > 0)
			{
				DualFunction nextFunction = nextFunctions.Pop();
				//DualFunction nextFunction = nextFunctions[0];
				//nextFunctions.RemoveAt(0);

				sortedFunctions.Add(nextFunction); // sorting fastlagt her

				foreach (KeyValuePair<DualFunction, List<DualFunction>> node in dependencyMap)
				{
					//if (dependencyMap[nextFunction].Contains(node.Key))
					if (node.Value.Contains(nextFunction)) // afhaengighed af nextFunction, dvs. nextFunction skal holdes i scope
					{
						node.Value.Remove(nextFunction);
						if (node.Value.Count == 0)
						{
							nextFunctions.Push(node.Key);
							//nextFunctions.Add(node.Key);
						}
					}
				}
			}
			//Console.WriteLine(sw.Elapsed);
			//Console.WriteLine("slut");

			// Check for consistency.
			foreach (KeyValuePair<DualFunction, List<DualFunction>> node in dependencyMap)
			{
				if (node.Value.Count != 0)
				{
					// This should never happen for sane functions.
					throw new Exception("Cyclic dependency found.");
				}
			}

			//Console.WriteLine("DONE");
			//Console.WriteLine("DONE");
			//Console.WriteLine("DONE");
			//Console.WriteLine("DONE");
			//Console.WriteLine("DONE");
			//Console.WriteLine("DONE");

			// Determine when functions go out of scope.
			outOfScopeMap = new Dictionary<DualFunction, List<DualFunction>>();
			for (int i = 0; i < sortedFunctions.Count; i++)
			{
				// The function depends on itself (with respect to the scope).
				int index = i;

				// Other dependencies.
				if (reverseDependencyMap.ContainsKey(sortedFunctions[i]))
				{
					foreach (DualFunction dependsOn in reverseDependencyMap[sortedFunctions[i]])
					{
						// Search beginning from the current function. Since the list of functions is sorted, all
						// functions depending on the current function must be located after the current index.
						// It's likely that the scope ends shortly after this, so this operation is usually very fast.
						index = Math.Max(index, sortedFunctions.IndexOf(dependsOn, index + 1)); // i + 1
					}
				}

				// Add the function at the index of the last function using it.
				if (!outOfScopeMap.ContainsKey(sortedFunctions[index]))
				{
					outOfScopeMap[sortedFunctions[index]] = new List<DualFunction>();
				}
				outOfScopeMap[sortedFunctions[index]].Add(sortedFunctions[i]);
			}

			//Console.WriteLine("DONE2");
		}
	}
}
